package interview;

public class link_node_sort {
    static class  Node{
        int val;
        Node next;
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
        public Node() {
        }
    }
    public static void main(String[] args) {
        //一个链表计数几点升序，偶数节点降序，求排序后的链表
        Node head = new Node();
        Node p = head;
        int n = 12;
        for (int i = 1; i < n; i++) {
            if(i % 2 == 0){
                p.next = new Node(n - i, null);
            }
            else
                p.next = new Node(i , null);
            p = p.next;
        }
        Node t = head.next;
        while(t != null){
            System.out.print(t.val + " ");
            t = t.next;
        }
        System.out.println();
        head = sortNode(head.next);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    //分为三步，首先是拆分链表
    //其次是逆转链表
    //最后是排序链表
    public static Node sortNode( Node head){
        //拆分链表
        if(head == null || head.next == null)
            return head;
        Node a = head;
        Node b = head.next;
        Node p1 = a, p2 = b;
        while(p1 != null && p2 != null){
            p1.next = p2.next;
            p1 = p1.next;
            if(p1 != null){
                p2.next = p1.next;
                p2 = p2.next;
            }
        }
        //拆分之后得到a, b
        //反转链表b
        p2 = null;
        Node cur = b, nextNode = cur;
        while(cur != null){
            nextNode = cur.next;
            cur.next = p2;
            p2 = cur;
            cur = nextNode;
        }
        p1 = a;
        Node ans = new Node();
        Node p = ans;
        //合并两个链表
        while(p1 != null && p2 != null){
            while(p1 != null && p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            while(p2 != null && p1 != null && p2.val <= p1.val){
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
        return ans.next;
    }
}
